Error-Correcting Codes
A fundamental problem in the field of data storage and communication is the development of practical decoding methods for error-correcting codes.
One very important class of error-correcting codes is the class of linear block error-correcting codes. Unless specified otherwise, any reference to a “code” in the following description should be understood to refer to a linear block error-correcting code.
The basic idea behind these codes is to encode a block of k information symbols using a block of N symbols, where N>k. The additional N-k bits are used to correct corrupted signals when they are received over a noisy channel or retrieved from faulty storage media.
A block of N symbols that satisfies all the constraints of the code is called a “code-word,” and the corresponding block of k information symbols is called an “information block.” The symbols are assumed to be drawn from a q-ary alphabet.
An important special case is when q=2. In this case, the code is called a “binary” code. In the examples given in this description, binary codes are assumed, although the generalization of the decoding methods described herein to q-ary codes with q>2 is straightforward. Binary codes are the most important codes used in practice.
FIG. 1 shows a conventional “channel coding” 100 with a linear block error-correcting code. A source 110 produces an information block 101 of k symbols u[a]. The information block is passed to an encoder 120 of the error-correcting code. The encoder produces a code-word x[n] containing N symbols 102.
The code-word 102 is then transmitted through a channel 130, where the code-word is possibly corrupted into a signal y[n] 103. The corrupted signal y[n] 103 is then passed to a decoder 140, which attempts to output a reconstruction 104 z[n] of the code-word x[n] 102.
Code Parameters
A binary linear block code is defined by a set of 2k possible code-words having a block length N. The parameter k is sometimes called the “dimension” of the code. Codes are normally much more effective when N and k are large. However, as the size of the parameters N and k increases, so does the difficulty of decoding corrupted messages.
The Hamming distance between two code-words is defined as the number of symbols that differ in two words. The distance d of a code is defined as the minimum Hamming distance between all pairs of code-words in the code. Codes with a larger value of d have a better error-correcting capability. Codes with parameters N and k are referred to as [N,k] codes. If the distance d is also known, then the codes are referred to as [N,k,d] codes.
Code Parity Check Matrix Representations
A linear code can be represented by a parity check matrix. The parity check matrix representing a binary [N,k] code is a matrix of zeros and ones, with M rows and N columns. The N columns of the parity check matrix correspond to the N symbols of the code. The number of linearly independent rows in the matrix is N-k.
Each row of the parity check matrix represents a parity check constraint. The symbols involved in the constraint represented by a particular row correspond to the columns that have a non-zero symbol in that row. The parity check constraint forces the weighted sum modulo-2 of those symbols to be equal to zero. For example, for a binary code, the parity check matrix
                    H        =                  [                                                    1                                            1                                            1                                            0                                            1                                            0                                            0                                                                    0                                            1                                            1                                            1                                            0                                            1                                            0                                                                    0                                            0                                            1                                            1                                            1                                            0                                            1                                              ]                                    (        4        )            represents the three constraintsx[1]+x[2]+x[3]+x[5]=0  (5)x[2]+x[3]+x[4]+x[6]=0  (6)x[3]+x[4]+x[5]+x[7]=0  (7)where x[n] is the value of the nth bit, and the addition of binary symbols is done using the rules of modulo-2 arithmetic, such that 0+0=1+1=0, and 0+1=1+0=1.
Error-Correcting Code Decoders
The task of a decoder for an error-correcting code is to accept the received signal after the transmitted code-word has been corrupted in a channel, and try to reconstruct the transmitted code-word. The optimal decoder, in terms of minimizing the number of code-word decoding failures, outputs the most likely code-word given the received signal. The optimal decoder is known as a “maximum likelihood” decoder. Even a maximum likelihood decoder will sometimes make a decoding error and output a code-word that is not the transmitted code-word if the noise in the channel is sufficiently great.
Another type of decoder, which is optimal in terms of minimizing the symbol error rate rather than the word error rate, is an “exact-symbol” decoder. This name is actually not conventional, but is used here because there is no universally agreed-upon name for such decoders. The exact-symbol decoder outputs, for each symbol in the code, the exact probability that the symbol takes on its various possible values, e.g., 0 or 1 for a binary code.
Iterative Decoders
In practice, maximum likelihood or exact-symbol decoders can only be constructed for special classes of error-correcting codes. There has been a great deal of interest in non-optimal, approximate decoders based on iterative methods. One of these iterative decoding methods is called “belief propagation” (BP). Although he did not call it by that name, R. Gallager first described a BP decoding method for low-density parity check (LDPC) codes in 1963.
Turbo Codes
In 1993, similar iterative methods were shown to perform very well for a new class of codes known as “turbo-codes.” The success of turbo-codes was partially responsible for greatly renewed interest in LDPC codes and iterative decoding methods. There has been a considerable amount of recent work to improve the performance of iterative decoding methods for both turbo-codes and LDPC codes, and other related codes such as “turbo product codes” and “repeat-accumulate codes.” For example a special issue of the IEEE Communications Magazine was devoted to this work in August 2003. For an overview, see C. Berrou, “The Ten-Year-Old Turbo Codes are entering into Service,” IEEE Communications Magazine, vol. 41, pp. 110-117, August 2003 and T. Richardson and R. Urbanke, “The Renaissance of Gallager's Low-Density Parity Check Codes,” IEEE Communications Magazine, vol. 41, pp. 126-131, August 2003.
Many turbo-codes and LDPC codes are constructed using random constructions. For example, Gallager's original binary LDPC codes are defined in terms of a parity check matrix, which consists only of 0's and 1's, where a small number of 1's are placed randomly within the matrix according to a pre-defined probability distribution. However, iterative decoders have also been successfully applied to codes that are defined by regular constructions, like codes defined by finite geometries, see Y. Kou, S. Lin, and M. Fossorier, “Low Density Parity Check Codes Based on Finite Geometries: A Rediscovery and More,” IEEE Transactions on Information Theory, vol. 47, pp. 2711-2736, November, 2001. In general, iterative decoders work well for codes with a parity check matrix that has a relatively small number of non-zero entries, whether that parity check matrix has a random or regular construction.
FIG. 2 shows a prior art system 200 with a decoder of an LDPC code based on BP. The system processes the received symbols iteratively to improve the reliability of each symbol based on the constraints, as given by the parity check matrix that specifies the code.
In a first iteration, the BP decoder only uses channel evidence 201 as input, and generates soft output messages 202 from each symbol to the parity check constraints involving that symbol. This step of sending messages from the symbols to the constraints is sometimes called the “vertical” step 210. Then, the messages from the symbols are processed at the neighboring constraints to feed back new messages 203 to the symbols. This step is sometimes called the “horizontal” step 220. The decoding iteration process continues to alternate between vertical and horizontal steps until a certain termination condition 204 is satisfied. At that point, hard decisions 205 are made for each symbol based on the output reliability measures for symbols from the last decoding iteration.
The precise form of the message update rules, and the meaning of the messages, varies according to the particular variant of the BP method that is used. Two particularly popular message-update rules are the “sum-product” rules and the “min-sum” rules. These prior-art message update rules are very well known, and approximations to these message update rules also have proven to work well in practice. In some variants of the BP method, the messages represent the log-likelihood that a bit is either a 0 or a 1. For more background material on the BP method and its application to error-correcting codes, see F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, “Factor Graphs and the Sum-Product Algorithm,” IEEE Transactions on Information Theory, vol 47, pp. 498-519, February 2001.
It is sometimes useful to think of the messages from symbols to constraints as being the “fundamental” independent messages that are tracked in BP decoding, and the messages from constraints to symbols as being dependent messages that are defined in terms of the messages from symbols to constraints. Alternatively, one can view the messages from constraints to symbols as being the “independent” messages, and the messages from symbols to constraints as being “dependent” messages defined in terms of the messages from constraints to symbols.
Bit-Flipping Decoders
Bit-flipping (BF) decoders are iterative decoders that work similarly to BP decoders. These decoders are somewhat simpler. Bit-flipping decoders for LDPC codes also have a long history, and were also suggested by Gallager in the early 1960's when he introduced LDPC codes. In a bit-flipping decoder, each code-word bit is initially assigned to be a 0 or a 1 based on the channel output. Then, at each iteration, the syndrome for each parity check is computed. The syndrome for a parity check is 0 if the parity check is satisfied, and 1 if it is unsatisfied. Then, for each bit, the syndromes of all the parity checks that contain that bit are checked. If a number of those parity checks greater than a pre-defined threshold are unsatisfied, then the corresponding bit is flipped. The iterations continue until all the parity checks are satisfied or a predetermined maximum number of iterations is reached.
A turbo-code is a concatenation of two smaller codes that can be decoded using exact-symbol decoders, see C. Berrou and A. Glavieux, “Near-Optimum Error-Correcting Coding and Decoding: Turbo-codes,” IEEE Transactions in Communications, vol. 44, pp. 1261-1271, October 1996. Convolutional codes are typically used for the smaller codes, and the exact-symbol decoders are usually based on the BCJR decoding method; see L. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate,” IEEE Transactions on Information Theory, pp. 284-287, March 1974 for a detailed description of the BCJR decoding method. Some of the code-word symbols in a turbo-code have constraints imposed by both codes. These symbols are called “shared symbols.” A conventional turbo-code decoder functions by alternately decoding the codes using their exact-symbol decoders, and utilizing the output log-likelihoods for the shared symbols determined by one exact-symbol decoder as inputs for the shared symbols in the other exact-symbol decoder.
The structure of a turbo-code constructed using two systematic convolutional codes 301 and 302 is shown schematically in FIG. 3. In this turbo-code, the shared symbols are the information bits for each of the convolutional codes.
The simplest turbo-decoders operate in a serial mode. In this mode, one of the BCJR decoders receives as input the channel information, and then outputs a set of log-likelihood values for each of the shared information bits. Together with the channel information, these log-likelihood values are used as input for the other BCJR decoder, which sends back its output to the first decoder and then the cycle continues.
Turbo Product Code
A turbo product code (TPC) is a type of product code wherein each constituent code can be decoded using an exact-symbol decoder. Product codes are well-known prior-art codes. To construct a product code from a [N1,k1,d1] code and a [N2,k2,d2] code, one arranges the code-word symbols in a N1 by N2 rectangle. Each symbol belongs to two codes—one a [N1,k1,d1] “vertical” code constructed using the other symbols in the same column, and the other a [N2,k2,d2] “horizontal” code constructed using the other symbols in the same row. The overall product code has parameters [N1N2,k1k2,d1d2].
The TPC is decoded using the exact-symbol decoders of the constituent codes. The horizontal codes and vertical codes are alternately decoded using their exact-symbol decoders, and the output log-likelihoods given by the horizontal codes are used as input log-likelihoods for the vertical codes, and vice-versa. This method of decoding turbo product codes is called “serial-mode decoding.”
Other Codes that can be Decoded Iteratively
There are many other codes that can successfully be decoded using iterative decoding methods. Those codes are well-known in the literature and there are too many of them to describe them all in detail. Some of the most notable of those codes are the irregular LDPC codes, see M. A. Shokrollahi, D. A. Spielman, M. G. Luby, and M. Mitzenmacher, “Improved Low-Density Parity Check Codes Using Irregular Graphs,” IEEE Trans. Information Theory, vol. 47, pp. 585-598 February 2001; the repeat-accumulate codes, see D. Divsalar, H. Jin, and R. J. McEliece, “Coding Theorems for ‘Turbo-like’ Codes,” Proc. 36th Allerton Conference on Communication, Control, and Computing, pp. 201-210, September, 1998; the LT codes, see M. Luby, “LT Codes,” Proc. Of the 43 Annual IEEE Symposium on Foundations of Computer Science, pp. 271-282, November 2002; and the Raptor codes, see A. Shokrollahi, “Raptor Codes,” Proceedings of the IEEE International Symposium on Information Theory, p. 36, July 2004.
Methods to Speed Up Iterative Decoders
BP and BF decoders for LDPC codes, decoders for turbo codes, and decoders for turbo product codes are all examples of iterative decoders that have proven useful in practical systems. A very important issue for all those iterative decoders is the speed of convergence of the decoder. It is desired that the number of iterations required before finding a code-word is as small as possible. A smaller number of iterations results in faster decoding, which is a desired feature for error-correction systems.
For turbo-codes, faster convergence can be obtained by operating the turbo-decoder in parallel mode, see D. Divsalar and F. Pollara, “Multiple Turbo Codes for Deep-Space Communications,” JPL TDA Progress Report, pp. 71-78, May 1995. In that mode, both BCJR decoders simultaneously receive as input the channel information, and then simultaneously output a set of log-likelihood values for the information bits. The outputs from the first decoder are used as inputs for the second iteration of the second decoder and vice versa.
FIG. 4 shows the difference between operating a turbo-code in serial 401 and parallel 402 modes for one iteration in each of the modes. In serial mode 401, the first decoder 411 operates first, and its output is used by the second decoder 412, and then the output from the second decoder is returned to be used by the first decoder in a next iteration. In parallel mode 402, the two decoders 421-422 operate in parallel, and the output of the first decoder is sent to the second decoder for the next iteration while simultaneously the output of the second decoder is sent to the first decoder.
Similarly to the case for turbo-codes, parallel-mode decoding for turbo product codes is described by C. Argon and S. McLaughlin, “A Parallel Decoder for Low Latency Decoding of Turbo product Codes,” IEEE Communications Letters, vol. 6, pp. 70-72, February 2002. In parallel-mode decoding of turbo product codes, the horizontal and vertical codes are decoded concurrently, and in the next iteration, the outputs of the horizontal codes are used as inputs for the vertical codes, and vice versa.
Group Shuffled Decoding
Finally, for BP decoding of LDPC codes, “group shuffled” BP decoding is described by J. Zhang and M. Fossorier, “Shuffled Belief Propagation Decoding,” Proceedings of the 36th Annual Asilomar Conference on Signals, Systems, and Computers, pp. 8-15, November 2002.
In ordinary BP decoding, as described above, messages from all bits are updated in parallel in a single vertical step. In group-shuffled BP decoding, the bits are partitioned into groups. The messages from a group of bits to their corresponding constraints are updated together, and then, the messages from the next group of bits are updated, and so on, until the messages from all the groups are updated, and then the next iteration begins. The messages from constraints to bits are treated as dependent messages. At each stage, the latest updated messages are used. Group shuffled BP decoding improves the performance and convergence speed of decoders for LDPC codes compared to ordinary BP decoders.
Intuitively, the reason that the parallel-mode decoders for turbo-codes and turbo product codes, and the group-shuffled decoders for LDPC codes speed up convergence is as follows. Whenever a message is updated in an iterative decoder, it becomes more accurate and reliable. Therefore, using the most recent version of a message, rather than older versions, normally increases speed convergence to the correct decoding.
Although the prior-art methods do give some improvement in speed of convergence, it is strongly desired to further improve convergence speed and performance. In many applications, the speed of decoding is of critical importance.